1. Field of the Invention
The present invention relates to computer-aided design of digital electronic circuits, and more particularly relates to a method of reformulating static circuit optimization problems in order to reduce size, degeneracy, and/or redundancy.
2. Brief Description of the Prior Art
As digital electronic circuits increase in size and complexity, automatic optimization of performance-critical designs increases in importance. Such automatic optimization can lead to better circuits and enhanced productivity. Static circuit optimization implies the determination of optimal transistor and wire sizes, on a static timing basis, while simultaneously taking into account all paths through the logic. The advantages of static optimization include increased designer productivity, since an optimal circuit is automatically determined; higher quality circuits, that is, faster, smaller, and/or lower power consumption; and the fact that all paths through the logic are simultaneously considered.
Reference should be had to FIG. 1, which depicts the flow of a typical prior art circuit optimization method. As shown at Block 102, a description of the circuit (or netlist) which is to be optimized can initially be prepared. "Netlist" is a generic term for a file containing a description of a circuit. The circuit description can then be read, as in Block 104, and a timing graph can be created based on the circuit description which has been read, as shown in Block 106. Timing constraints can then be formulated which correspond to the circuit description, as shown at Block 108, and then additional constraints and objective functions can be added as necessary, per Block 109. Finally, the circuit can be optimized as per Block 110.
Block 106 is optional, as a timing graph need not always be created, instead, the timing constraints associated with the problem statement can be formulated directly. In this case, the constraints formulated in Block 108 will correspond to the problem statement. When a timing graph is employed, per Block 106, Block 108 can include formulating constraints which correspond to the timing graph. Any additional constraints and objective functions which are necessary can be added per Block 109, as above.
One exemplary method of static circuit optimization is disclosed in U.S. patent application Ser. No. 950,782 of Strenski, filed Oct. 15, 1997, the disclosure of which is expressly incorporated herein by reference. Although the Strenski method is advantageous, and achieves the benefits set forth above, there are still problems with the Strenski method, and indeed, with all known prior art methods of circuit optimization. Chief among these is computational complexity. Large digital circuits, with many components, can result in extremely complex optimization problems which may require many hours of CPU time to solve. Accordingly, it would be highly desirable to improve prior art methods.
Further, in prior art methods, the formulation of the optimization problem suffers from numerical disadvantages such as redundancy and degeneracy. In a degenerate case, a LaGrange multiplier associated with an active constraint is zero. In a redundant case, removal of a constraint without any other manipulation doesn't change the problem. All active redundant constraints give rise to a degenerate problem. However, there are degenerate problems without redundant constraints. From an optimization perspective, these types of problems often have multiple equivalent solutions and are relatively difficult to solve.
In view of the foregoing, there is a need in the prior art for a method of reformulating static optimization problems for digital circuits which can reduce the size of problem, as well as potentially reducing degeneracy and redundancy.